// https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> ans;

        int row = 0, col = 0, index = 0;
        for (int i = 0; i < m * n; i++) {
            ans.emplace_back(matrix[row][col]);
            visited[row][col] = true;

            int nextRow = row + dir[index][0];
            int nextCol = col + dir[index][1];

            if (nextRow < 0 || nextCol < 0 || nextRow >= m || nextCol >= n || visited[nextRow][nextCol]) {
                index = (index + 1) % 4;
                nextRow = row + dir[index][0];
                nextCol = col + dir[index][1];
            }
            row = nextRow;
            col = nextCol;
        }

        return ans;
    }
};